package algorithm.string;

import java.util.HashSet;
import java.util.Set;

class Solution {





    //最长相等前后缀不包含的子串就是最小重复子串: (字符串s - 最长相等前后缀 = 最小重复子串)
    // 这里拿字符串s：abababab 来举例，ab就是最小重复单位，
    //最长相等前缀：ababab ；对应的最长相等后缀：ababab 。两者与字符串s的间隙：ab

    //方式1: kmp
public boolean repeatedSubstringPattern(String s) {
    //一、先求next数组。再判断是否有重复的子字符串？
    // 1、初始化：定义两个指针i和j。j指向前缀末尾位置(也可以代表 相同前后缀的长度 )，
    // i指向后缀末尾位置(一直在往后遍历，增加中)。
    //2、处理前后缀末尾(i、j)不相同的情况：就要向前回退，找 前一个元素在next数组里的值（子串的相同前后缀的长度）。
    // (发生冲突的前一位 在前缀表所对应的值是多少。)
    //3、处理前后缀相同的情况：就同时向后移动i 和j 说明找到了相同的前后缀，
    int j =0; //i=0开始
    int[] next = new int[s.length()];
    next[0] = 0;
    //2
    for (int i = 1; i <s.length(); i++){
        while (j>0 && s.charAt(i) != s.charAt(j)) j = next[j-1];
        // 找 前一个元素在next数组里的值（子串的相同前后缀的长度）。
        //如果j = 0，就是回退到最起点，0处了，不能再退了。
        if (s.charAt(i) == s.charAt(j)) next[i] = j+1;
        // == 后 就过了，两者都继续向后移动。
        ++j;
    }

    //二、再判断是否有重复的子字符串？
    // 最长相等前后缀的长度为：next[len - 1]。数组长度为：len。
    int len = s.length();
    if (next[len-1] ==0) return false;
    //末尾字符不同。肯定不是。

    int subS = len - next[len - 1];

    // 数组的长度正好可以被 (数组长度-最长相等前后缀的长度) 整除 ，说明该字符串有重复的子字符串。
    return len % subS == 0;
}




    //方式2: 使用了语言自带的字符串查找函数
    public boolean repeatedSubstringPattern2(String s) {

        String ss = s + s;
        //刨除 s + s 的首字符和尾字符，这样避免搜索出原来的 2 个 s中的一个
        String sub = ss.substring(1, ss.length() - 1);
        // int indexOf(String str):
        // 返回指定字符在字符串中第一次出现处的索引，如果此字符串中没有这样的字符，则返回 -1。
        // 只要两个s拼接在一起，里面还出现一个s的话，就说明是由重复子串组成。
        int res = sub.indexOf(s);
//        return res >=0 ? true : false;
        return res >=0 ;
    }


    //  方法一：KMP
    public int strStr(String haystack, String needle) {
        // 主串 haystack, 子串needle
        int[] next = new int[needle.length()];
        //先生成Next数组，最长相等前后缀
        getNext(next, needle);

        //j 指向子串起始位置
        int j = 0;
        //遍历主串，用needle去匹配
        for (int i = 0; i < haystack.length(); i++) {
            //接下来就是 子串与 主串  进行比较。
            //如果不相同，j就要从next数组里寻找下一个匹配的位置。(回退)
            while (j>0 && needle.charAt(j) != haystack.charAt(i)) j = next[j-1];
            //如果 子串与 主串 的元素 相同，那么i 和 j 都向后移动， 判断下个元素
            if (needle.charAt(j) == haystack.charAt(i)) j++;

            //j顺利到结尾了，全比较完了。返回 haystack 中第一个匹配项的下标
            if (j == needle.length()) return i-needle.length()+1;
        }
        return -1;//不匹配：则返回  -1
    }

    //计算前缀表:最长相等前后缀
    private void getNext(int[] next, String s) {
        //步骤：
        // 1、初始化：定义两个指针i和j，j指向前缀末尾位置，i指向后缀末尾位置。
        int j =0; // j位置：前缀：以第一个字符开头的,下标从0开始。
        next[0] = 0; //首先对于第一个字符，显然不存在比它短的前后缀，所以next直接为0。

        //遍历子串，生成 Next数组：0已经有值了。
        for (int i = 1; i < s.length(); i++){
            //2、处理前后缀末尾(i、j)不相同的情况：就要向前回退，找 前一个元素在next数组里的值（子串的相同前后缀的长度）。
            // (发生冲突的前一位 在前缀表所对应的值是多少。)
            // 用while：因为可能退多步。与暴力破解相比，这步没有直接全退完。
            //使用了kmp匹配，相当于前半段和后半段的匹配,利用已经掌握的信息来避免重复的运算
            while (j>0 && s.charAt(i) != s.charAt(j)) j = next[j-1];

            //3、处理前后缀相同的情况：就同时向后移动i 和j 说明找到了相同的前后缀，
            // 同时还要将j（前缀的长度）赋给next[i], 因为next[i]要记录相同前后缀的长度。
            if(s.charAt(i) == s.charAt(j))  j++;
            next[i] = j;//j增加后再赋值。
        }
    }


    //    方法二：暴力匹配
    public int strStr1(String haystack, String needle) {
        int res= -1;
        for (int i = 0; i < haystack.length()-needle.length()+1; i++) {

            for (int j = 0; j < needle.length(); j++) {
                if (haystack.charAt(i+j) != needle.charAt(j)){
                    break;
                }else {
                    if (j== needle.length()-1) return i;
                }
            }

        }
        return res;
    }





    public  int[] intersection(int[] nums1, int[] nums2) {
        //set集合判断集合中是否有无...求交集
        //遍历nums1的元素存Set，遍历判断是否包含num2的元素。是就存结果set里(set也要去nums2的重复)。
        //Set.contains(object)
        Set<Integer> set = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        for (int i = 0; i < nums1.length; i++) {
            set.add(nums1[i]);
        }
        for (int i = 0; i < nums2.length; i++) {
            if (set.contains(nums2[i])) resSet.add(nums2[i]);

        }
        int[] resInts = resSet.stream().mapToInt(Integer::valueOf).toArray();
        return resInts;
    }


}